MOD = 998244353
TRANS = [6, 3, 7, 4, 1, 0]
s = input().strip()
dp = [0] * 7 + [1]
for c in map(int, s):
dp1 = [0] * 8
for i in range(8):
for k in TRANS:
if c:
dp1[k & i] += dp[i]
elif (k & i) == 0:
dp1[i] += dp[i]
dp = [x % MOD for x in dp1]
n = int(s, base=2) + 1
print((n**3 + 3 * n**2 - n - 3 * sum(dp)) % MOD)
2099. Find Subsequence of Length K With the Largest Sum | 1608A - Find Array |
416. Partition Equal Subset Sum | 1446. Consecutive Characters |
1618A - Polycarp and Sums of Subsequences | 1618B - Missing Bigram |
938. Range Sum of BST | 147. Insertion Sort List |
310. Minimum Height Trees | 2110. Number of Smooth Descent Periods of a Stock |
2109. Adding Spaces to a String | 2108. Find First Palindromic String in the Array |
394. Decode String | 902. Numbers At Most N Given Digit Set |
221. Maximal Square | 1200. Minimum Absolute Difference |
1619B - Squares and Cubes | 1619A - Square String |
1629B - GCD Arrays | 1629A - Download More RAM |
1629C - Meximum Array | 1629D - Peculiar Movie Preferences |
1629E - Grid Xor | 1629F1 - Game on Sum (Easy Version) |
2148. Count Elements With Strictly Smaller and Greater Elements | 2149. Rearrange Array Elements by Sign |
2150. Find All Lonely Numbers in the Array | 2151. Maximum Good People Based on Statements |
2144. Minimum Cost of Buying Candies With Discount | Non empty subsets |